package basic_datastructure.linear;

public class Stack {
    private int[] item;     //数组实现栈
    private int N;          //栈的大小
    public Stack(){}
    public Stack(int capacity){
        this.item = new int[capacity];
    }

    /**
     * 数组的扩容
     * @param capacity
     */
    public void resize(int capacity){
        int[] copy = new int[capacity];
        for (int i = 0; i < N; i++){
            copy[i] = item[i];
        }
        item = copy;
    }
    /**
     * 入栈操作，入栈位置为 N
     * @param num
     */
    public void push(int num){
        if(N == item.length){
            resize(item.length * 2);
        }
        item[N++] = num;
    }

    /**
     * 出栈操作，出栈位置为 N - 1
     * @return
     */
    public int pop(){
        int res = item[--N];
        item[N] = 0;
        //当 N 为数组长度的 四分之一， 栈容量缩小一半
        if(N > 0 && N == item.length / 4){
            resize(item.length / 2);
        }
        return res;
    }

    public boolean isEmpty(){
        return N == 0;
    }
}
